use std::ptr::{copy, swap, swap_nonoverlapping, write};

pub trait SearchTreeBase<K, V> {
    fn new() -> Self;

    fn insert(&mut self, key: K, val: V) -> bool;

    fn delete(&mut self, key: K) -> bool;

    fn update(&mut self, key: K, val: V);

    fn query(&self, key: K) -> Option<V>;

    fn where_val<F: FnMut(&V) -> bool>(&self, f: F) -> Vec<V>;

    fn where_key<F: FnMut(&K) -> bool>(&self, f: F) -> Vec<K>;

    fn to_vector(&self) -> Vec<(K, V)>;

    fn min_key(&self) -> Option<K>;

    fn min_val(&self) -> Option<K>
    where
        V: Ord;

    fn max_key(&self) -> Option<K>;

    fn max_val(&self) -> Option<K>
    where
        V: Ord;

    fn clear(&mut self);

    fn size(&self) -> usize;
}

#[inline]
pub fn max<T: Ord>(a: T, idx_a: u64, b: T, idx_b: u64) -> (T, u64) {
    match a > b {
        true => (a, idx_a),
        false => (b, idx_b),
    }
}

#[inline]
pub fn min<T: Ord>(a: T, idx_a: u64, b: T, idx_b: u64) -> (T, u64) {
    match a < b {
        true => (a, idx_a),
        false => (b, idx_b),
    }
}

#[inline]
pub unsafe fn insert_at_slice<T>(slice: &mut [T], val: T, idx: usize, len: usize) {
    assert!(idx <= len, "the index is out of the bound");
    let ptr = slice.as_mut_ptr().add(idx);
    if len - idx > 0 {
        copy(ptr, ptr.add(1), len - idx);
    }
    write(ptr, val);
}

#[inline]
pub unsafe fn delete_at_slice<T>(slice: &mut [T], idx: usize, len: usize) {
    assert!(idx < len, "the index is out of the bound");
    let ptr = slice.as_mut_ptr().add(idx);
    if len - idx - 1 > 0 {
        copy(ptr.add(1), ptr, len - idx - 1);
    }
}

#[inline]
pub unsafe fn copy_from_slice<T>(src: &[T], dst: &mut [T], size: usize) {
    assert!(src.len() >= size && dst.len() >= size);
    copy(src.as_ptr(), dst.as_mut_ptr(), size);
}

#[inline]
pub unsafe fn swap_slices<T>(x: &mut [T], y: &mut [T], size: usize) {
    assert!(x.len() >= size && y.len() >= size);
    swap_nonoverlapping(x.as_mut_ptr(), y.as_mut_ptr(), size);
}

#[inline]
pub unsafe fn swap_in_slice_at<T>(x: &mut [T], i: usize, j: usize) {
    assert!(x.len() > i && x.len() > j);
    let ptr = x.as_mut_ptr();
    if i != j {
        swap(ptr.add(i), ptr.add(j));
    }
}
